import Tree.TreeDP;
import com.sun.prism.PresentableState;

import javax.swing.tree.TreeNode;
import java.util.*;

public class WWC {


    //2 普通解法
    public static int minBags(int apple){
        if (apple < 0 )return -1;
        int bag6 = -1;
        int bag8 = apple /8;
        int rest = apple-8*bag8;
        while (bag8 >=0 && rest<24){
            int restUse6 = minBagsBase6(rest);
            if (restUse6 != -1){
                bag6 = restUse6;
                break;
            }
            rest = apple-  8 * (-- bag8);
        }
        return bag6 == -1?-1:bag6+bag8;
    }

    // 如果剩余的苹果rest可以被装6个苹果的袋子搞定, 返回袋子数量,不能就返回-1
    private static int minBagsBase6(int rest) {
        return rest %6 == 0? (rest /6) :-1;
    }
    //打表法
    public static int minBagAwesome(int apple){
        if ((apple & 1) != 0){
            return -1;
        }
        if (apple < 18){
            return apple == 0 ? 0 : (apple == 6 || apple == 8) ? 1:
                    (apple == 12 || apple == 14|| apple == 16 )? 2:-1;
        }
        return (apple-18)/8 +3;

    }


    //  n 个草放一堆
    public static String winner1(int n) {
        // 0  1 2  3  4
        // 后 先 后 先 先
        if (n < 5) return (n == 0 || n == 2) ? "后手" : "先手";
        // n >= 5
        int base = 1; // 先手决定吃的草
        // 有问题
        while (base <= n) {
            // 当前一共 n 份草, 先手吃掉的是base份 , n - base是留给后手的草
            //当前过程是先手, 但是在子过程中是后手 , 判断我先手可能赢的机会
            if (winner1(n - base).equals("后手")) {
                return "先手";
            }
            if (base > n / 4) {//防止溢出
                break;
            }
            base *= 4;
        }
        return "后手";
    }
    //查看前代码用数学规律得出来的最优解, 代码
    public static String winner2(int n){
        if (n % 5 == 0 || n % 5 == 2){
            return "先手";
        }
        return "后手";
    }
    //返回函数
    public static int f(){
        return (int)(Math.random()*5)+1;

    }
    // 等概率返回0 和1 的函数
    public static int r01(){
        int res =0;
        do {
            res = f();
        }while (res == 3);
        return res <3 ? 0:1;
    }
    public static int g(){
        // 1~7
        int res =0;
        do {
            res = (r01() << 2)+(r01()<<1)+r01();
        }while (res == 7);
        return res+1;
    }
    // 左右括号问题
    public static int needParentheses(String str){
        int count =0;
        int ans =0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '('){
                count++;
            }else {
                if (count == 0){
                    ans++;
                }else {
                    count--;
                }
            }
        }
        return count+ans;
    }
    // 找差值
    public static List<List<Integer>> allPair(int[] arr, int k){
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            set.add(arr[i]);
        }
        List<List<Integer>> res = new LinkedList<>();
        for (Integer cur:set) {
            if (set.contains(cur+k)){
                res.add(Arrays.asList(cur,cur+k));
            }
        }
        return res;
    }
    //最多平均值
    public static int maxOps(int[] arr1 , int[] arr2){
        double sum1 = 0;
        for (int i = 0; i < arr1.length; i++) {
            sum1+=(double) arr1[i];
        }
        double sum2 =0;
        for (int i = 0; i < arr2.length; i++) {
            sum2 = (double) arr2[i];
        }
        if (avg(sum1, arr1.length) == avg(sum2, arr2.length)) {
            return 0;
        }
        int[] arrMore = null;
        int[] arrLess = null;
        double sumMore = 0;
        double sumLess = 0;
        if (avg(sum1, arr1.length) > avg(sum2, arr2.length)) {
            arrMore =arr1;
            sumMore =sum1;
            arrLess =arr2;
            sumLess = sum2;
        }else {
            arrMore =arr2;
            sumMore =sum2;
            arrLess =arr1;
            sumLess = sum1;
        }
        Arrays.sort(arrMore);
        HashSet<Integer> setLess = new HashSet<>();
        for (int num:arrLess) {
            setLess.add(num);
        }
        int moresize = arrMore.length;// 平均值大的还剩下几个数
        int lesssize = arrLess.length;// 平均值小的还剩下几个数
        int ops = 0;//操作了多少次
        for (int i = 0; i < arrMore.length; i++) {
            double cur =(double) arrMore[i];
            if (cur < avg(sumMore,moresize) && cur > avg(sumLess,lesssize)
            && ! setLess.contains(arrMore[i])){
                sumMore -=cur;
                moresize --;
               sumLess += cur;
               lesssize++;
               setLess.add(arrMore[i]);
               ops++;
            }
        }
        return ops;
    }

    private static double avg(double sum1, int length) {
        return sum1 / length;
    }
    // 最深的括号
    public static int maxLentght(String  s){
        if (s == null || s.equals(""))return 0;
        char[] str = s.toCharArray();
        int[] dp = new int[str.length];
        int pre =0;
        int res =0;
        for (int i = 1; i < str.length; i++) {
            if (str[i] == ')'){
                pre = i - dp[i-1]-1;//与str[i]匹配的左括号的位置pre
                if (pre >= 0 && str[pre] == '('){
                    dp[i] = dp[i-1] + 2+(pre>0?dp[pre-1]:0);
                }
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
    public static Stack<Integer> zWT(Stack<Integer> stack){
        Stack<Integer> res = new Stack<>();
        while (!stack.isEmpty()){
            int k = stack.pop();
            if (res.isEmpty() || k < res.peek()){
                res.push(k);
            }else {
                while (!res.isEmpty() && k > res.peek()){
                    stack.push(res.pop());
                }
                res.push(k);
            }
        }
        while (!res.isEmpty()){
            stack.push(res.pop());
        }
        return stack;
    }
    // 数字转字符
   public static int  converWays(int num){
        if (num < 1)return 0;
        return process(String.valueOf(num).toCharArray(), 0);
   }
   //
   public static int process(char[] str,int index){
        if (index == str.length)return 1;
        // index 后序有数字字符
        if (str[index] == '0')return 0;
        // 不以 0 开头
        int res = process(str,index+1);

        if (index == str.length-1)return res;
        //
        if (((str[index] -'0')*10+str[index+1]-'0')< 27){
            res += process(str,index+2);
        }
        return res;
   }
   // 二叉树求: 以根节点到叶节点的最大权值
    public static int process2(TreeDP.Node X){
        if (X.left == null && X.right == null)return X.value;
        int next =Integer.MIN_VALUE;
        if (X.left != null)next =process2(X.left);
        if (X.right!=null)next = Math.max(next,process2(X.right));

        return X.value+next;
    }
    // 判断一个数是否存在在 , 一个每行与没列有序的二维数组中
    public static boolean isMire(int[][] arr , int k){
        for (int j = arr[0].length-1; j >= 0; j--) {
            if (arr[0][j] < k){
                int i = 0;
                while (i < arr.length && j >= 0){
                    if (arr[i][j] == k)return true;
                    else if (arr[i][j] < k) i++;
                    else {
                        i=0;
                        j--;
                    }
                }
            }
        }
        return false;
    }
    //给定一个二维数组,0都在数组左边, 1都在数组右边问,哪一行的1数量最多,请返回
    public static int fHHS(int[][] arr ){
       int i =0;
        for (int j = arr[0].length; j >= 0 ; j--) {
            if (arr[i][j-1] == 0){
                while (arr[i][j-1] == 0){
                    i++;
                }
            }
        }
        return i;
    }
    // 洗衣机问题 Packing Machine
    public static int MinOps(int[] arr){
        if (arr == null || arr.length == 0)return 0;
        int size =arr.length;
        int sum =0;
        for (int i = 0; i < size; i++) {
            sum+=arr[i];
        }
        if (sum % size != 0)return -1;
        int avg = sum /size;
        int leftsum =0;
        int ans =0;
        for (int i = 0; i < arr.length; i++) {
            // 负需要输入,  正需要输出
            int leftRest = leftsum - i*avg;
            int rightRest = (sum-leftsum-arr[i])-(size-i-1)*avg;

            if (leftRest < 0 && rightRest<0){
                ans = Math.max(ans,Math.abs(leftRest)+Math.abs(rightRest));
            }else {
                ans = Math.max(ans,Math.max(Math.abs(leftRest),Math.abs(rightRest)));
            }
            leftsum +=arr[i];
        }
        return ans;
    }
    // 二维数组之螺旋打印
    public static void spiralOrderPrint(int[][] arr){
        int tr =0;
        int tc =0;
        int dr = arr.length-1;
        int dc = arr[0].length-1;
        while (tr <= dr && tc <=dc){
            printEdge(arr,tr++,tc++,dr--,dc--);
        }
    }


    private static void printEdge(int[][] arr, int a, int b, int c, int d) {
        if (a == c){
            // 说明俩个点在同一行上
            for (int i = b; i <= d; i++) {
                System.out.println(arr[a][i]+" ");
            }
        }else if (b == d){
            for (int i = a; i <= c; i++) {
                System.out.println(arr[i][b]+" ");
            }
        }else {
            int curC=b;
            int curR=a;
            while (curC != d){
                System.out.println(arr[a][curC] +" ");
                curC++;
            }
            while (curR != c){
                System.out.println(arr[c][b] +" ");
                curR++;
            }
            while (curC != b){
                System.out.println(arr[c][curC] +" ");
                curC++;
            }
            while (curR != a){
                System.out.println(arr[curR][a] +" ");
                curR++;
            }
        }
    }
    // 二维数组顺时针旋转90度
    public static void rotate(int[][] arr){
        int tr=0 ,tc=0,dr =arr.length-1,dc=arr[0].length-1;
        while (tr<dr){
            rotateEdge(arr,tr++,tc++,dr--,dc--);
        }
    }
    public static void rotateEdge(int[][] m,int a,int b , int c,int d){
        int tmp =0;
        for (int i = 0; i < d-b; i++) {
            tmp = m[a][b+i];
            m[a][b+i] = m[c-i][b];
            m[c-i][b] = m[c][d-i];
            m[c][d-i] = m[a+i][d];
            m[a+i][d] = tmp;
        }
    }
    // 斜的方式打印
    public static void printMatrZigzag(int[][] arr){
        int ar=0,ac=0,br=0,bc=0;
        int endR = arr.length-1;
        int endC = arr[0].length-1;
        boolean from = false;
        while (ar != endR+1){
            printLevel(arr,ar,ac,br,bc,from);
            ar=ac == endC?ar+1:ar;// a到了最后一列 a的行才增加
            ac= ac == endC?ac:ac+1;// a的列到了最后一列才不变, 否则就增加
            bc = br == endR?bc+1:bc;
            br =br == endR?br:br+1;
            from =!from;
        }
        System.out.println();
    }

    private static void printLevel(int[][] arr, int tr, int tc, int dr, int dc, boolean from) {
        if (from){
            while (tr != dr+1) System.out.println(arr[tr++][tc--]+" ");
        }else {
            while (dr != tr-1){
                System.out.println(arr[dr--][dc++]+" ");
            }
        }

    }

    /* 给你一个字符串 s , s中只有 '.'和'X'俩种字符
    路灯可以影响左中右三个位置
    问你至少需要多少灯,可以把点都点亮
    * */
    public static int minLight(String s){
        // 贪心策略
        if (s == null || s.length()==0){
            return 0;
        }
        char[] str = s.toCharArray();
        int ans =0;
        int i=0;
        while (i< str.length){
            if (str[i] == 'x'){
                i++;
            }else {
                //当你来到 i 位置, 一定要保证之前的灯,不会影响到 i位置
               ans++;
               if (i+1 == str.length){
                   break;
               }else {
                   if (str[i+1] == 'x'){
                       i=i+1;
                   }else {
                       i=i+3;
                   }
               }
            }
        }
        return ans;
    }
    //
    public static int nodeNum(TreeDP.Node head){
        if (head == null)return 0;
        return bs(head,1,mostLeftLevel(head,1));
    }
    // 如果 node在第level层
    // 求以node为头的子树,最大深度是多少
    private static int mostLeftLevel(TreeDP.Node head, int level) {
        while (head != null){
            level++;
            head = head.left;
        }
        return level-1;
    }

    public static int bs(TreeDP.Node node, int level, int h){
        if (level == h)return 1;
        if (mostLeftLevel(node.right,level+1) == h){
            return (1 << (h-level))+bs(node.right,level+1,h);
        }else {
            return (1 << (h-level-1))+bs(node.left,level+1,h);
        }
    }
    //保证 i位置对应 i+1的数
    public static void printNum(int[] arr){
        if (arr == null || arr.length ==0){
            return;
        }
        for (int val:arr) {
            modify(val,arr);
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != i+1){
                System.out.println(i+1);
            }
        }
    }

    private static void modify(int val, int[] arr) {
        while (arr[val-1] != val){
            int tmp = arr[val-1];
            arr[val-1] = val;
            val =tmp;
        }
    }


    public static int minCC(int add,int time,int del,int start,int end){
        if (start > end)return -1;
        return process5(0,end,add,time,del,start,end*2,(end-start)/2*add);
    }
    /*
    preM 之前花了多少钱
    aim 目标
    add time del 固定
    cur 当前的人气
    limitAim 人气达到什么程序不用尝试
    LimitCC  硬币达到什么程度不用尝试
    * */
    public static int process5(int preM,int aim,int add,int time,int del,
    int cur,int limitAim ,int limitConin){
        if (preM > limitConin){
            return Integer.MAX_VALUE;
        }
        if (cur < 0){
            return Integer.MAX_VALUE;
        }
        if (cur > limitAim){
            return Integer.MAX_VALUE;
        }
        if (aim == cur){
            return preM;
        }
        int min = Integer.MAX_VALUE;
        int p1 = process5(preM+add,aim,add,time,del,cur+2,limitAim,limitConin);
        if (p1 != Integer.MAX_VALUE){
            min = p1;
        }
        int p2 = process5(preM+del,aim,add,time,del,cur-2,limitAim,limitConin);
        if (p2 != Integer.MAX_VALUE){
            min = Math.min(p2,min);
        }
        int p3 = process5(preM+time,aim,add,time,del,cur*2,limitAim,limitConin);
        if (p3 != Integer.MAX_VALUE){
            min = Math.min(p3,min);
        }
        return min;
    }

    //给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
    public static List<Integer>  spiralOrder(int[][] matrix) {
        int x1 =0 ,y1=0;
        int x2 =matrix.length-1,y2=matrix[0].length-1;
        List<Integer> list = new ArrayList<>();
        while (x1 <= x2 && y1 <= y2){
            process1(matrix,x1,y1,x2,y2,list);
            x1++;y1++;
            x2--;y2--;
        }
        return list;
    }
    private static void process1(int[][] arr, int x1,int y1,int x2, int y2,List<Integer> list){
        for (int i = y1; i <= y2; i++) {
           list.add(arr[x1][i]);
        }
        for (int i = x1+1; i <= x2; i++) {
            list.add(arr[i][y2]);
        }
        for (int i = y2-1; i >= y1&& x1 != x2; i--) {

            list.add(arr[x2][i]);
        }
        for (int i = x2-1; i > x1; i--) {
            list.add(arr[i][y1]);
        }
    }

    public static void main(String[] args) {
        int[][] arr = {{1,2,3,4}, {5,6,7,8},{9,10,11,12}};
        printMatrZigzag(arr);
    }



}
